1. Field of the Invention
This invention relates to the field of electronic commerce, and more particularly to a method and apparatus for managing key revocation in a cryptographic environment.
2. Background Art
In a computerized environment, a digital certificate ("certificate") is used to attach a degree of assurance to information (e.g., a cryptographic key) associated with a certificate. A certificate is digitally signed by the entity that offers it as a voucher for the authenticity of the information. If the certificate is issued by a trusted third party, it is assumed that its information content is valid. However, as is discussed below, largely due to information "aging", current techniques for determining the validity of a certificate are inadequate.
Digital Signatures
One of the purposes of a digital signature is to link an electronic document with an owner of the private key corresponding to a particular public key. Additionally, a digital signature can be used to determine whether an electronic document has been altered during transmission of the document from the sender to the recipient.
One form of digital signature uses a message digest. A message digest is a value that is generated when an electronic document is passed through a one way encryption process ("digesting process") such as a hashing routine. An ideal digesting process is one for which the probability that two different electronic documents will generate the same message digest is near zero. In this form of digital signature, both the sender and the recipient need to know which digesting process is being used. The sender generates the electronic document, and generates a message digest by passing the electronic document through the digesting process. The sender encrypts the resulting message digest with the sender's private key. The result, the encrypted message digest, then becomes the digital signature of the electronic document. The digital signature may be appended to the electronic document or kept as a separate entity.
Digital Certificates
Certificates have been devised to address some of the uncertainties inherent in public key cryptography. Public key cryptography uses a two key pair, typically referred to as a public key and a private key. These two keys are different but constitute a matched key pair. In normal practice, the owner of a key pair keeps the private key secret, but freely distributes the public key.
One uncertainty relates to the identity of the owner of the private key that corresponds to the public key, because the public key is widely available and subject to malicious modification. It is possible, for example, that a public key may be circulated that fraudulently purports to be the public key of party A, but the corresponding private key of which is actually held by party B.
Certificates are intended to provide a degree of assurance as to the identity of the holder of the private key corresponding to a particular public key. A certificate constitutes a certification by a certification authority ("CA") that a particular public key is the public key of a particular entity, and that this entity is the holder of the corresponding private key. That is, a certificate can be used to certify the authenticity of information such as a public key.
The degree of assurance provided by a certificate depends on a number of factors, including the reputation of the CA issuing the certificate, the thoroughness of the procedures used by the CA in issuing the certificate, and the degree of confidence in the CA's public key. Some CAs issue different levels of certificates, corresponding to different levels of investigation performed by the CA during evaluation of an application.
The certificate may be appended to an electronic document, or the recipient of an electronic document may obtain a copy of the certificate from the issuing CA or other certificate repository.
The certificate itself is an electronic document. Although a variety of formats exist, a certificate typically includes, among other items, the name of the certification authority, the name of the certificate holder, the expiration date of the certificate, the public key of the certificate holder, and the digital signature of the certification authority. The certificate constitutes a certification by the certification authority that the holder of the certificate is the owner of the public key specified in the certificate, and, by implication, is therefore the holder of the corresponding private key.
For example, a certificate is issued by a CA (e.g., Verisign) to warrant to a party, A, that a cryptographic key belongs to another party, B. The CA, C, is trusted by both A and B. Without a certificate, another party, D, could send a key to A in the name of B. A would use D's key to encrypt messages that A intended to be accessible only by B. Instead, D could access the message by intercepting and deciphering it using the key it sent to A. If, however, A obtained B's key from C contained in a certificate, there is little opportunity for D to intercede with a counterfeit key.
FIG. 1 provides an example of a certificate. Certificate 100 contains a Version Number 110 that identifies the certificate format. Serial Number 120 is unique within a particular CA and identifies certificate 100. Digital Signature Algorithm identifier 130 identifies the algorithm used to create signature 190 and any parameters needed for the specified algorithm. Certification Authority 140 identifies the CA that issued certificate 100 and signed it with Signature 190.
Period of Validity 150 specifies the dates in which certificate 100 is operational (i.e., in its operational period). Certificate 100 is not valid until a certain date and becomes invalid after a certain date. Certificate 100 contains information associated with a user. The user's identification (e.g., name) is contained in User Name 160. The user's public key is contained in the certificate in User Public Key 170. The certificate may also contain Other User Data 180, such as E-mail address or date of birth of the user.
Signature 190 is used by a recipient to authenticate certificate 100. Signature 190 can be generated using a number of different techniques. For example, signature 190 can be the result of computing a message digest of fields 110-180 of certificate 100, and encrypting the message digest using the CA's private key. The CA's public key is used to verify the signature of certificate 100.
A certificate can be made available directly from a CA. That is, A can contact the CA to obtain B's certificate. Receiving B's certificate directly from the CA increases the chance that it is a valid certificate. However, B's certificate may also be available at a repository other than the CA such as a local certificate database that is accessible to A via a network.
The certificate provided by a CA has an operable life. A CA warrants the accuracy of the information during that time period, a period of validity. The CA does not warrant information before or after the period of validity.
A certificate contains the dates (see period of validity 150 in FIG. 1) during which it is operational. During its operational period, a certificate is valid unless it has been suspended or revoked. A suspension is a temporary hold that is placed on a certificate. If a certificate is revoked, the operational period of the certificate is permanently terminated from the time of revocation forward. After its operational period, a certificate is considered to be expired. A CA reports the state of a certificate that has been revoked or suspended in a certificate revocation list ("CRL").
Digital Certificate Revocation and CRLs
If a certificate is compromised in some manner, it must be rendered inoperable (e.g., revoked) during its validity period. To provide notification of certificate revocations, a CA provides a list of certificates that have been revoked in a CRL. A CRL is issued on a periodic basis which can be as frequently as daily. It is necessary to consult each and every CRL that has been issued by the CA during the validity period of the certificate, to determine whether a certificate obtained from the CA was revoked prior to its expiration. A CRL is typically provided as a print out or can be sent to a user in the form of an electronic message. Distribution of a CRL introduces delay into the notification process.
During its period of validity, a certificate is stored in a certificate database. It is possible to query the repository to determine whether a certificate that is still in its period of validity has been revoked or suspended. When a certificate is no longer in its period of validity, it is removed from the certificate database. There is no ability to perform an automated search of a certificate to determine its validity status ("status") at a particular point in time once it is outside its period of validity. If, for example, it might be necessary to determine whether a certificate was still in effect (i.e., not revoked or suspended) five years ago.
The only record that is currently available of the status of a certificate outside its validity period is contained in the set of CRLs issued by the CA. To determine the status of a certificate that is no longer in its validity period, it is necessary to consult each of the issued CRLs to determine whether the certificate is listed in one of the CRLs. This is a process that is susceptible to errors. The set of CRLs that is consulted must contain all of the issued CRLs to determine with any certainty the status of a certificate. Further, each CRL in the set of CRLs must be reviewed to determine whether it references the certificate. The volume of the CRLs that must be maintained by each user grows very large, as it becomes necessary to check a certificate against the CRLs even years after its expiration date. CRLs are never truly retired.
If the certificate is found in one of the CRLs, it is possible to determine the status of the certificate at the time of that CRL. If, however, the certificate is not included in one of the CRLs consulted, the soundness of the conclusion that the certificate is valid rests on whether any CRL or any entry in a CRL that identifies the certificate was overlooked during the process. It is possible that notification of revocation of the certificate is contained in a missing CRL. Further, the task is tedious and prone to error. Therefore, even if the set of CRLs is complete, it is possible to overlook an entry in one of the CRLs that references the certificate in question. There is currently no mechanism for storing and retrieving information about the status of a certificate whether or not the certificate is within its validity period.
A certificate is valid during its operational period. Before or after its operational period, the certificate should not be used. As described above, a certificate can become unusable (e.g., revoked or suspended) during its operational period. For example, a user's private key can become compromised. Since the certificate contains the public key that is associated with the compromised private key, the certificate should not be used.
To render a certificate unusable, the CA revokes or suspends the certificate. On a periodic basis, a CA issues a CRL that identifies the certificates that have been revoked or suspended since the last CRL was issued. FIG. 2 provides an example of a CRL report format. CRL 200 contains the name of the issuer of the CRL 202, the date of the CRL's issuance 204, and the date of the next CRL issuance 206.
An entry for each certificate that has been revoked or suspended since the last issued CRL is contained in area 214 of the report. Each entry contains the Certificate Serial Number 208, the Suspension or Revocation date and time 210, and possibly the reason for the suspension or revocation (e.g., private key is compromised) 212.
Each entry's Certificate Serial Number 208 in area 214 must be reviewed to determine whether a specific certificate is included in CRL 200. Area 214 can contain one or more entries. CRL 200 could be multiple pages. The following is an example of a certificate's serial number: EQU 63992a43ef2e97a757cdb49c4c1d6014
The serial number in the example contains thirty two alphanumeric characters. If the entries in area 214 are sorted using field 208 (i.e., by serial number), it would be necessary to locate the area of the report at which the certificate's serial number would be located and verify by looking at the entries contained at that location. The entries could be very similar such that only one or two characters differ between the report entries and the certificate in question making it easy to mistakenly identify an entry as specifying or not specifying the certificate.
FIG. 3 provides an illustration of a set of CRLs. The set of CRLs consist of CRLs 304, 306, 308, 310, and 312. CRLs 306, 308, and 312 consist of more than one page. CRLs 304, 306, 308, 310, and 312 must be consulted to determine whether certificate 302 was revoked at a certain date and time. That is, each of the CRLs must be reviewed to determine whether the serial number assigned to certificate 302 is contained therein. Entry 322 in CRL 310 identifies certificate 302 as having been revoked.
Certificate Validation
A certificate must be checked against all outstanding CRLs each time before it is used to determine whether it is valid. The set of CRLs that could contain information about a revoked or suspended certificate are those issued during the validity period of the certificate. FIG. 4 provides a flow for validating a certificate at any point in time. At step 402, the certificate's serial number is obtained from the certificate. At step 406 (i.e., "all CRLs in set reviewed?"), a determination is made whether all CRLs in the set have been reviewed to locate the certificate. If so, it is assumed that the certificate has not been revoked or suspended during the period in question. If some CRLs remain, the next CRL in the set is reviewed at step 410.
The process documented in FIG. 4 may be performed manually or automatically, by a computer program. It is slow and tedious. The strength of the conclusion that a certificate is valid is dependent on whether the set of CRLs was a complete set (i.e., contained all of the issued CRLs) and the thoroughness of the individual or program that performs the review. The process is inefficient, prone to error, and inconclusive.